package package2;

import java.util.ArrayList;

public class RedBlackTree<T extends Comparable<T>> {

    public final static String COLOR_BLACK = "black";
    public final static String COLOR_RED = "red";

    public final static String SIDE_LEFT = "left";
    public final static String SIDE_RIGHT = "right";

    public RBNode<T> root;

    public RBNode<T> add(T data) {
        if (this.isEmpty()) {
            RBNode<T> newRBNode = new RBNode<T>(data, null, null, null, COLOR_BLACK, null);
            this.root = newRBNode;
            return newRBNode;
            
        } else {
            RBNode<T> node = root;
            RBNode<T> nodeToInsert = new RBNode<T>(data, null, null, null, COLOR_RED, null);
            boolean finished = false;
            while (!finished) {
                if (node.compareTo(data) > 0) {
                    if (node.left == null) {
                        nodeToInsert.side = SIDE_LEFT;
                        nodeToInsert.parent = node;
                        node.left = nodeToInsert;
                        finished = true;
                    } else {
                        node = node.left;
                    }
                } else {
                    if (node.right == null) {
                        nodeToInsert.side = SIDE_RIGHT;
                        nodeToInsert.parent = node;
                        node.right = nodeToInsert;
                        finished = true;
                    } else {
                        node = node.right;
                    }
                }
            }
            return nodeToInsert;
        }
    }
    
    public void insert(T data) {
        this.checkInsertCases(this.add(data));
    }
    
    private void checkInsertCases(RBNode<T> current) {
        boolean finished = false;
        while (!finished) {
            System.out.println("Current: " + current.data);
            if(current == this.root) {
                finished = true;
            } else if (current.parent.isBlack()) {
                System.out.println("Reached Insert Case 1");
                finished = true;
            } else if (current.getUncle() == null || current.getUncle().isBlack()) {
                if (current.parent.side == SIDE_LEFT) {
                    if (current.side == SIDE_LEFT) {
                        System.out.println("Reached Insert Case 2");
                        current.parent.paintBlack();
                        current.getGrandParent().paintRed();
                        this.rotateRight(current.getGrandParent());
                        finished = true;
                    } else {
                        System.out.println("Reached Insert Case 3");
                        current.getGrandParent().paintRed();
                        current.paintBlack();
                        this.leftRightRotation(current);
                        finished = true;
                    }
                } else {
                    if (current.side == SIDE_RIGHT) {
                        System.out.println("Reached Insert Case 4");
                        current.getGrandParent().paintRed();
                        current.parent.paintBlack();
                        this.rotateLeft(current.getGrandParent());
                        finished = true;
                    } else {
                        System.out.println("Reached Insert Case 5");
                        current.getGrandParent().paintRed();
                        current.paintBlack();
                        this.rightLeftRotation(current);
                        finished = true;
                    }
                }
            } else {
                System.out.println("Reached Insert Case 6");
                current.parent.paintBlack();
                current.getUncle().paintBlack();
                if(current.getGrandParent() == this.root) {
                    finished = true;
                } else {
                    current.getGrandParent().paintRed();
                    current = current.getGrandParent();
                }
            }
        }
    }

    private boolean isEmpty() {
        return (this.root == null);
    }

    public void printTree() {
        this.root.printNodes();
    }

    public RBNode<T> rotateRight(RBNode<T> current) {
        RBNode<T> leftChild = current.left;
        current.left = leftChild.right;
        
        if(current.left != null) {
            current.left.parent = current;
            current.left.side = SIDE_LEFT;
        }

        leftChild.right = current;
        leftChild.side = current.side;
        leftChild.parent = current.parent;

        // Moves up the tree and updates relationships
        RBNode<T> parent = current.parent;
        RBNode<T> child = leftChild;
        while (parent != null) {
            if (child.side == SIDE_LEFT) {
                parent.left = child;
            } else {
                parent.right = child;
            }
            child = parent;
            parent = parent.parent;
        }
        this.root = child;

        current.parent = leftChild;
        current.side = SIDE_RIGHT;

        return leftChild;
    }

    public RBNode<T> rotateLeft(RBNode<T> current) {
        RBNode<T> rightChild = current.right;
        current.right = rightChild.left;
        
        if(current.right != null) {
            current.right.parent = current;
            current.right.side = SIDE_RIGHT;
        }
        

        rightChild.left = current;
        rightChild.side = current.side;
        rightChild.parent = current.parent;

        // Moves up the tree and updates relationships
        RBNode<T> parent = current.parent;
        RBNode<T> child = rightChild;
        while (parent != null) {
            if (child.side == SIDE_LEFT) {
                parent.left = child;
            } else {
                parent.right = child;
            }
            child = parent;
            parent = parent.parent;
        }
        this.root = child;

        current.parent = rightChild;
        current.side = SIDE_LEFT;

        return rightChild;
    }

    public void printTreePreOrder() {
        this.root.printPreOrder();
    }

    public ArrayList<RBNode<T>> getNodesPreOrder(ArrayList<RBNode<T>> nodes, RBNode<T> current) {
        if (current == null) {
            return nodes;
        }
        nodes.add(current);
        this.getNodesPreOrder(nodes, current.left);
        this.getNodesPreOrder(nodes, current.right);

        return nodes;
    }
    
    public void leftRightRotation(RBNode<T> b) {
        RBNode<T> c = b.getGrandParent();
        RBNode<T> a = b.parent;
        
        a.right = b.left;
        if(a.right != null) {
            a.right.side = SIDE_RIGHT;
            a.right.parent = a;
        }
        b.left = a;
        a.parent = b;
        b.side = c.side;
        
        b.parent = c.parent;
        if(b.parent != null) {
            if(b.side == SIDE_LEFT) {
                b.parent.left = b;
            } else {
                b.parent.right = b;
            }
        }
        
        c.left = b.right;
        if(c.left != null) {
            c.left.side = SIDE_LEFT;
            c.left.parent = c;
        }
        b.right = c;
        c.parent = b;
        
        if(c == this.root) {
            this.root = b;
        }
        
    }
    
    public void rightLeftRotation(RBNode<T> b) {
        RBNode<T> c = b.getGrandParent();
        RBNode<T> a = b.parent;
        
        a.left = b.right;
        if(a.left != null) {
            a.left.side = SIDE_LEFT;
            a.left.parent = a;
        }
        b.right = a;
        a.parent = b;
        b.side = c.side;
        
        b.parent = c.parent;
        if(b.parent != null) {
            if(b.side == SIDE_LEFT) {
                b.parent.left = b;
            } else {
                b.parent.right = b;
            }
        }
        
        c.right = b.left;
        if(c.right != null) {
            c.right.side = SIDE_RIGHT;
            c.right.parent = c;
        }
        b.left = c;
        c.parent = b;
        
        if(c == this.root) {
            this.root = b;
        }
    }
    
    public void inOrder(RBNode<T> temp){
        if(temp == null) return;
        inOrder(temp.left);
        System.out.println(temp.data + " Color: " + temp.color);
        inOrder(temp.right);
    }
    
    public static void main(String[] args){
        RedBlackTree testing = new RedBlackTree();
        testing.insert(17);
        testing.insert(18);
        testing.insert(20);
        testing.insert(21);
        testing.insert(43);
        testing.insert(2);
        testing.insert(230);
        testing.insert(12);
        testing.inOrder(testing.root);
    }

}